import java.util.*;

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int[] levelOrder1(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode cur = root;

        while (cur != null || !q.isEmpty()) {
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
            list.add(cur.val);
            cur = q.poll();
        }
        Integer[] integers = list.toArray(new Integer[list.size()]);
        int[] ret = new int[integers.length];
        Arrays.setAll(ret, i -> integers[i]);
        return ret;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>(0);
        }
        ArrayList<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode cur = root;
        boolean flag= false;
        q.offer(cur);
        while (cur != null || !q.isEmpty()) {
            int len = q.size();
            ArrayList<Integer> tmp = new ArrayList<>(len);
            while ((len--) > 0) {
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
                tmp.add(cur.val);
                q.poll();
                cur = q.peek();
            }
            if(flag){
                Collections.reverse(tmp);
            }
            flag=!flag;
            ret.add(tmp);
        }
        return ret;
    }

    public static void main(String[] args) {
        Solution.TreeNode node1 = new Solution.TreeNode(3);
        Solution.TreeNode node2 = new Solution.TreeNode(9);
        Solution.TreeNode node3 = new Solution.TreeNode(20);
        Solution.TreeNode node4 = new Solution.TreeNode(15);
        Solution.TreeNode node5 = new Solution.TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        Solution solution = new Solution();
        solution.levelOrder(node1);

    }
}